#include <bits/stdc++.h>
using namespace std;

/*
166. 分数到小数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证 答案字符串的长度小于 104 。

 

示例 1：

输入：numerator = 1, denominator = 2
输出："0.5"
示例 2：

输入：numerator = 2, denominator = 1
输出："2"
示例 3：

输入：numerator = 4, denominator = 333
输出："0.(012)"
 

提示：

-231 <= numerator, denominator <= 231 - 1
denominator != 0
*/

// 法一
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        string ans;
        using ll = long long; // 用long long避免整数溢出
        ll d = denominator, n = numerator;

        // 处理整除情况：直接返回整数结果
        if (n % d == 0) {
            ans = to_string(n / d);
            return ans;
        }

        // 非整除情况：处理整数部分、符号和小数部分
        ll k = n * d; // 用乘积符号判断分子分母是否异号（异号则k<0）
        ll x = n / d; // 整数部分（可能带符号）

        // 处理符号：分子分母异号则结果为负
        if (k < 0) {
            ans += "-";
        }
        x = abs(x);          // 整数部分取绝对值，避免符号干扰
        ans += to_string(x); // 加入整数部分
        ans += ".";          // 加入小数点

        // 初始化小数部分计算：取余数（n - 整数部分*x）
        n = abs(n);
        d = abs(d);
        ll fz = n - x * d;

        // 记录(商, 余数)对应的小数位位置，用于检测循环
        // 同一(商,余数)重复出现 → 后续小数循环
        map<ll, map<ll, ll>> mp;
        int left = -1, right = -1; // 循环段的起始/结束位置（小数位内相对位置）
        int pos = 0;               // 当前小数位序号（从1开始）

        // 计算小数部分
        while (true) {
            fz *= 10; // 余数乘10，模拟小数位递进
            pos++;    // 当前小数位序号+1

            // 有限小数：余数可整除分母，添加商后结束
            if (fz % d == 0) {
                ans += to_string(fz / d);
                break;
            }
            // 无限小数：计算当前商和新余数
            else {
                ll a = fz / d; // 当前小数位的商
                ll b = fz % d; // 新余数（用于下一轮计算）
                fz = b;

                // 若(商,余数)已出现，标记循环段
                if (mp[a].count(b)) {
                    left = mp[a][b]; // 循环段起始位置（之前记录的序号）
                    right = pos;     // 循环段结束位置（当前序号）
                    break;
                }
                // 记录(商,余数)对应的位置，添加当前小数位
                mp[a][b] = pos;
                ans += to_string(a);
            }
        }

        // 处理循环小数：插入括号
        if (left != -1) {
            string res;
            int k = 0;
            // 拼接整数部分和小数点
            while (ans[k] != '.') res += ans[k++];
            res += ".";

            // 拼接循环段之前的小数位
            for (int i = k + 1; i < k + left; i++) res += ans[i];
            res += "(";

            // 拼接循环段并添加右括号
            for (int i = left; i < right; i++) {
                res += ans[i + k];
            }
            res += ")";
            return res;
        }

        // 无循环：直接返回结果
        return ans;
    }
};

// 法二 初始思路
class Solution {
public:
    using ll = long long;
    string fractionToDecimal(int numerator, int denominator) {
        // 异号
        bool isNeg = false;
        if (numerator != 0 && denominator != 0) isNeg = (numerator < 0) ^ (denominator < 0);

        ll num = abs(static_cast<ll>(numerator));
        ll den = abs(static_cast<ll>(denominator));

        // 整数 取余  或者转int截取后面
        string ans = to_string(num / den);
        ll rem = num % den;     // 后面的小数

        if (rem == 0)   return isNeg ? "-" + ans : ans;

        // 有小数 要append一个
        ans += ".";
        // 哈希表记录余数位置：key=余数，value=余数在res中的索引（用于检测循环）
        unordered_map<ll, int> rem_pos;

        while (rem != 0) {
            // 余数已出现：说明从上次位置开始循环，插入括号
            if (rem_pos.find(rem) != rem_pos.end()) {
                // 开始插括号
                ans.insert(rem_pos[rem], "(");
                ans.append(")");
                break;
            }
            // 记录当前余数的位置（当前res长度即下一个字符的索引）
            rem_pos[rem] = ans.size();
            // 余数乘10，模拟小数位计算
            rem *= 10;
            // 当前商作为小数位，加入结果
            ans += to_string(rem / den);
            // 更新余数（取模后继续循环）
            rem = rem % den;
        }
        if (isNeg)  ans = '-' + ans;

        return ans;
    }
};

// 法二的优化
class Solution {
public:
    using ll = long long; // 简化long long类型声明，提升代码简洁性
    string fractionToDecimal(int numerator, int denominator) {
        // 优化1：提前处理分子为0的特殊情况（0除以任何非0数结果都是0，无需后续逻辑）
        if (numerator == 0) {
            return "0";
        }

        // 优化2：简化符号判断（分子已非0，直接判断异号，无需额外非0检查）
        bool isNeg = (numerator < 0) ^ (denominator < 0);

        // 转换为绝对值计算，避免符号干扰；用ll防止INT_MIN取绝对值溢出
        ll num = abs(static_cast<ll>(numerator));
        ll den = abs(static_cast<ll>(denominator));

        // 计算整数部分（直接整除，结果转字符串）
        string ans = to_string(num / den);
        ll remainder = num % den; // 余数用于后续小数部分计算

        // 无小数部分：处理符号后直接返回
        if (remainder == 0) {
            return isNeg ? "-" + ans : ans;
        }

        // 有小数部分：先添加小数点
        ans += ".";

        // 优化3：哈希表命名更直观，记录余数首次出现的位置（key=余数，value=对应小数在ans中的索引）
        unordered_map<ll, int> remainderIndex;

        // 计算小数部分，同时检测循环
        while (remainder != 0) {
            // 余数重复出现：说明从首次位置开始循环，插入括号后退出
            if (remainderIndex.count(remainder)) {
                ans.insert(remainderIndex[remainder], "("); // 循环起始位置插左括号
                ans += ")"; // 末尾插右括号
                break;
            }

            // 记录当前余数的位置（ans当前长度 = 下一个小数字符的索引）
            remainderIndex[remainder] = ans.size();
            // 余数×10模拟小数位递进，计算下一位小数
            remainder *= 10;
            ans += to_string(remainder / den); // 追加当前小数位
            remainder %= den; // 更新余数，准备下一轮计算
        }

        // 处理负号（最后统一加负号，避免中间逻辑干扰）
        if (isNeg) {
            ans = "-" + ans;
        }

        return ans;
    }
};

// 法四
#include <cmath>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0)
            return "0";

        std::string res;
        if ((numerator < 0) ^ (denominator < 0))
            res += '-';

        long long num = std::abs(static_cast<long long>(numerator));
        long long den = std::abs(static_cast<long long>(denominator));
        res += to_string(num / den);
        long long remain = num % den;
        if (remain == 0)
            return res;

        res += '.';
        unordered_map<long long, int> remainPosition;
        while (remain != 0) {
            if (remainPosition.find(remain) != remainPosition.end()) {
                res.insert(remainPosition[remain], "(");
                res += ')';
                break;
            }

            remainPosition[remain] = res.size();
            remain *= 10;
            res += to_string(remain / den);
            remain %= den;
        }

        return res;
    }
};